|
|
Monadic NP sets
Putzer, Martin ; Krajíček, Jan (vedoucí práce) ; Honzík, Radek (oponent)
Jako zobecněná spektra se označují třídy konečně axiomatisovatelné v existenční druhořádové logice s relací platnosti omezenou na konečné struktury. Jest známým faktem, že korrespondují dle Faginovy věty s prvky složitostní třídy NP. Prob- lém uzavřenosti NP na komplementaci se tedy redukuje na problém uzavřenosti zobecněných spekter na komplementaci. Důkaz P ̸= NP, za předpokladu, že ono tvrzení skutečně platí, by tak mohl spočívat v nalezení konkretního zobecněného spektra (a tedy třídy v NP), jehož doplněk, jsa arci v coNP, by nebyl prvkem NP. Hledání takového důkazu ovšem též nepřineslo úspěch. Částečné rozřešení tohoto problému (an sám je toliko speciálním příkladem obecnějšího tak zvaného prob- lému Asserova) přinesla Fagin-Hájkova věta, tvrdící, že jistá podtřída NP, třída tak zvaných monadických NP množin vskutku netvoří třídu uzavřenou na kom- plementaci. Reprodukce Faginova původního důkazu této věty, spolu s uvedením veškerého potřebného apparátu, je cílem této práce. 1
|
host ::
RSS.